package sol.leetcode;

import def.ListNode;
import def.TreeNode;
import utils.LinkedListUtils;

/**
 * Convert Sorted List to Binary Search Tree
 */
public class Issue109 {
    public TreeNode sortedListToBST(ListNode head) {
        return createBST(head, null);
    }

    public TreeNode createBST(ListNode head, ListNode tail) {
        ListNode slow = head;
        ListNode fast = head;
        if (head == tail) return null;

        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode thead = new TreeNode(slow.val);
        thead.left = createBST(head, slow);
        thead.right = createBST(slow.next, tail);
        return thead;
    }

    public static void main(String[] args) {
        ListNode head = LinkedListUtils.create(1, 2, 3, 4, 5);
        Issue109 sol = new Issue109();
        TreeNode root = sol.sortedListToBST(head);

        System.out.println(root.val);
    }
}
